package lc20240526;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class TwoNumbersSum {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(9);
//        l1.next=new ListNode(4);
//        l1.next.next=new ListNode(3);

        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(9);
        l2.next.next = new ListNode(9);
        l2.next.next.next = new ListNode(9);
        l2.next.next.next.next = new ListNode(9);
        l2.next.next.next.next.next = new ListNode(9);
        l2.next.next.next.next.next.next = new ListNode(9);
        l2.next.next.next.next.next.next.next = new ListNode(9);
        l2.next.next.next.next.next.next.next.next = new ListNode(9);
        l2.next.next.next.next.next.next.next.next.next = new ListNode(9);
        TwoNumbersSum t = new TwoNumbersSum();
        ListNode listNode = t.addTwoNumbers1(l1, l2);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    //错误示范，容易出现溢出问题。
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new ArrayDeque<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }

        Deque<Integer> stack2 = new ArrayDeque<>();
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        long a = 0;
        long b = 0;
        while (!stack1.isEmpty()) {
            a = a * 10 + stack1.pop();
        }
        while (!stack2.isEmpty()) {
            b = b * 10 + stack2.pop();
        }
        long sum = a + b;
        if (sum==0){
            return new ListNode(0);
        }
        int remainder = (int) (sum % 10);

        ListNode res = new ListNode(remainder);
        ListNode cur = res;
        while (sum != 0) {
            remainder = (int) (sum % 10);
            sum /= 10;
            cur.next = new ListNode(remainder);
            cur = cur.next;
        }
        return res.next;
    }
    public ListNode addTwoNumbers1(ListNode l1, ListNode l2){
        //借助两个队列，而不是两个栈。
        Deque<Integer> queue1 = new ArrayDeque<>();
        while (l1 != null) {
            queue1.add(l1.val);
            l1 = l1.next;
        }

        Deque<Integer> queue2 = new ArrayDeque<>();
        while (l2 != null) {
            queue2.add(l2.val);
            l2 = l2.next;
        }

        ListNode res=new ListNode(0);
        ListNode p=res;
        int carry=0;
        while (!queue1.isEmpty()||!queue2.isEmpty()||carry!=0){
            int sum=carry;
            if (!queue1.isEmpty()){
                sum+=queue1.poll();
            }
            if (!queue2.isEmpty()){
                sum+=queue2.poll();
            }
            carry=sum/10;
            p.next=new ListNode(sum%10);
            p=p.next;
        }
        return res.next;
    }
}
